#include <cstdio>

using namespace std;
typedef long long LL;
LL binary_pow1(LL a,LL b,LL m)
{
    if (b==0)
    {
        return 1;
    }
    if (b&1)
    {
        return a*binary_pow1(a,b-1,m)%m;
    }
    else
    {
        LL mul=binary_pow1(a,b/2,m);
        return mul*mul%m;
    }
}
LL binary_pow2(LL a,LL b,LL m)
{
    LL ans=1L;
    for (;b ;b>>=1 )//b>>=1 is equivalent to b/=2
    {
        if (b&1)//b&1 is equivalent to b%2
        {
            ans=ans*a%m;
        }
        a=a*a%m;//a^{2^n}=a^{2^n-1}^2
    }
    return ans;
}
int main_109()
{
    printf("%lld\n",binary_pow1(1200000000,1500000000,152));
    printf("%lld",binary_pow2(1200000000,1500000000,152));
	return 0;
}
